Week 1 Assignment-Percolation

发表于 | 分类于 |

Application of Union-Find

大三终于下定决心要结束自己的咸鱼生活了，于是开始刷起Coursera的Algorithms: 4th Part 1，在家吹着空调写着代码岂不是美滋滋~这是第一周的编程练习，主要是对Union-Find(并查集)的应用。

问题描述


Week 1:Assignment
如上图所示，这是一个简单的渗透(Percolation)模型。一个N*N的方格网络，里面的方格有两种不同的状态，打开（白色）或者关闭（黑色）。我们可以把他看做一个水槽，黑色就是墙壁，从上方倒水的话，水也会从上往下灌满连通的所有白格子。
如果在一个水槽模型中，水能从最上方流至底端，也就是说，底层存在打开的格子并与上方的格子连通，即称这个模型是渗透的。

这是个在科学界比较著名的问题。假设在一个网格区域内，每个格子打开的概率为 P，关闭的概率就是 1-P。人们找到了一种概率分布，当N足够大时, 有一个阈值P*, 使得当p < p*时候，任意的N*N网格，几乎不能被渗透， 并且当p > p*, 基本能够被渗透。p*没有准确的数值解。
我们要做的就是使用Union-Find中的Union操作来合并上下左右已经打开的格子，用Connect操作来判断顶端和底端是否连通。随机地打开一些格子，来模拟渗透的整个过程。


再通过一定的测试数据，使用Monte Carlo simulation方法来估算P*的值。

整个过程可以简化为：

  • 将所有格子初始化为关闭
  • 重复以下过程直到系统为渗透的
    • 所有关闭的格子中随机挑选一个
    • 打开它
  • 估算的渗透阈值为：打开的格子数 / 总格子数
  • 这里还有几个任务
  • 需要我们完善
  • ​

算法思路

1. Percolation

根据Percolation给出的API，用于合并打开的格子和判断是否渗透

1
2
3
4
5
6
7
8
public class Percolation {
   public Percolation(int N)              // create N-by-N grid, with all sites blocked
   public void open(int i, int j)         // open site (row i, column j) if it is not already
   public boolean isOpen(int i, int j)    // is site (row i, column j) open?
   public boolean isFull(int i, int j)    // is site (row i, column j) full?
   public boolean percolates()            // does the system percolate?
   public int numberOfOpenSites()   // number of OpenSites
}

在创建了N*N的网格后（ 左上和右下坐标分别为(1,1)和(N,N) ）初始化一个WeightedQuickUnionUF对象（包含在官方提供的algs4.jar包中，里面有很多可以直接用的API，import即可）。
注意WeightedQuickUnionUF对象中进行Union-Find操作使用的是一维数组，所以在Percolation中要注意将直角坐标转换为对应的一维数组的index
如果把这个问题看做一个动态连通性问题，在之前的slide中，导师也提到了一种巧妙地方法。

在顶端和底端分别设置一个虚节点，与第一行和第N行的节点都建立连接，最后只需要判断顶和底部虚节点是否连通就可以了，这样大大减少了复杂性，但是也会带来一些小问题，后面再说。

2. PercolationStats

1
2
3
4
5
6
7
8
public class PercolationStats {
   public PercolationStats(int n, int t)  // perform T independent computational experiments on an N-by-N grid
   public double mean()          // sample mean of percolation threshold
   public double stddev()       // sample standard deviation of percolation threshold
   public double confidenceLo()      // returns lower bound of the 95% confidence interval
   public double confidenceHi()      // returns upper bound of the 95% confidence interval
   public static void main(String[] args)   // test client (described below)
}

使用 n x n 网格进行 T 次独立实验，打印出样本平均值（sample mean）、样本标准差（sample standard deviation）和 95% 的置信区间。

算法优化

在使用顶部和底部虚节点的情况下，会出现backwash的情况，对于一些与bottom连通的结点，即便其于top不连通，但是因为bottom和top连通了，最终会导致这些结点也是full的。

2017-07-11 at 8.58 PM

看见我圈起来的那几个格子没，它们其实不应该连通，这种现象称作Backwash(回水)。
一开始我没想到这个。。然后再加上一堆bug，包括很多Code Style的细节，比如不能是用tab而是要转成4个space….导致前几次commit的分数都惨不忍睹。。。在看了课程讨论中各种大牛的回答后，大致是用下面这个方法，才不至于超时或者复杂度过高

Backwash解决方案

isFull()用来判断结点是否与top连通，需要注意的是，isFull和下面的percolates()并不是一个意思，percolation用来判断整个matrix是否上下连通，考虑的是总体情况，而对于某一个结点而言，它可能是full的（与top连接），但是并不在percolation的路径上，而这里也是产生backwash的主要原因

所以我们可以用两张表来维护格子之间的关系

1
2
uf = new WeightedQuickUnionUF(N * N + 2);
uf1 = new WeightedQuickUnionUF(N * N + 1);

uf的最后一行是连通的，uf1不连通，其他地方都一样。
如果要检查是否是渗透模型percolates()，就用uf。
如果要具体看每一个格子是否有水isFull()，就用uf1。
这样虽然占用的内存资源大了一块，但是省下了依次检查最下一行每一个格的时间。

运行结果

1
2
javac -cp ~/Code/Algorithms\ 4th/algs4.jar PercolationVisualizer.java Percolation.java // 编译 
java -cp ~/Code/Algorithms\ 4th/algs4.jar: PercolationVisualizer sedgewick60.txt //运行

好啦，官方提供了好多很有意思的test case. 他们帮你写好了一个PercolationVisualizer，运行后的效果…

又比如

很魔性有没有😂
AC后感觉又有了学习的动力~

源代码

See in github